package org.sselab.leetcode;

import java.util.Stack;

/**
 * @author pinker on 2017/11/22
 */
public class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Integer size1 = 0, size2 = 0;
    Stack<ListNode> stack1 = listToStack(l1, size1);
    Stack<ListNode> stack2 = listToStack(l2, size2);
    int carry = 0;
    int tmp;
    ListNode node = null, child = null;
    while (!stack1.isEmpty() && !stack2.isEmpty()) {
      node = stack1.peek();
      node.next = child;
      tmp = stack1.pop().val + stack2.pop().val + carry;
      carry = tmp / 10;
      node.val = tmp % 10;
      child = node;
    }
    Stack<ListNode> stack = stack1.isEmpty() ? stack2 : stack1;
    while (!stack.isEmpty()) {
      node = stack.peek();
      node.next = child;
      tmp = stack.pop().val + carry;
      carry = tmp / 10;
      node.val = tmp % 10;
      child = node;
    }
    if (carry > 0) {
      node = new ListNode(carry);
      node.next = child;
    }
    return node;
  }

  Stack<ListNode> listToStack(ListNode node, Integer size) {
    ListNode cursor = node;
    Stack<ListNode> stack = new Stack<>();
    while (cursor != null) {
      stack.push(cursor);
      size++;
      cursor = cursor.next;
    }
    return stack;
  }
}

class ListNode {
  int val;
  ListNode next;

  ListNode(int x) {
    val = x;
  }
}
